package cn.zifangsky.tree.binarysearchtree;

import org.junit.Test;

public class BinarySearchTreeNodeOperations {

	/**
	 * 中序遍历二叉搜索树：将得到一个有序递增序列
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void pirntByInOrder(BinarySearchTreeNode<Integer> root){
		if(root != null){
			pirntByInOrder(root.getLeft());
			System.out.print(root.getData() + " ");
			pirntByInOrder(root.getRight());
		}
	}
	
	/**
	 * 在二叉搜索树中查找元素
	 * 思路：
	 * 		如果当前节点大小不等于目标元素，那么当目标元素小于当前节点大小就查找左子树，相反则查找右子树
	 * 原因：	二叉搜索树的所有左子树节点的元素小于根节点元素，所有右子树节点的元素大于根节点元素
	 * 
	 * @时间复杂度 O(n)
	 * @param root
	 * @param data
	 * @return
	 */
	public BinarySearchTreeNode<Integer> findData(BinarySearchTreeNode<Integer> root,int data){
		if(root == null){
			return null;
		}
		
		if(data == root.getData().intValue()){
			return root;
		}else if(data < root.getData().intValue()){
			return findData(root.getLeft(),data);
		}else{
			return findData(root.getRight(),data);
		}
	}
	
	/**
	 * 非递归版本：在二叉搜索树中查找元素
	 * @时间复杂度 O(n)
	 * @param root
	 * @param data
	 * @return
	 */
	public BinarySearchTreeNode<Integer> findDataNoRecursion(BinarySearchTreeNode<Integer> root,int data){
		while (root != null) {
			if(data == root.getData().intValue()){
				return root;
			}else if(data < root.getData().intValue()){
				root = root.getLeft();
			}else{
				root = root.getRight();
			}
		}
		
		return null;
	}
	
	/**
	 * 在二叉搜索树中查找最小元素
	 * 思路：
	 * 		根据二叉搜索树的定义最左边的节点为最小元素
	 * @时间复杂度 O(n)
	 * @param root
	 * @param data
	 * @return
	 */
	public BinarySearchTreeNode<Integer> findMin(BinarySearchTreeNode<Integer> root){
		if(root == null){
			return null;
		}
		
		if(root.getLeft() == null){
			return root;
		}else{
			return findMin(root.getLeft());
		}
	}
	
	/**
	 * 非递归版本：在二叉搜索树中查找最小元素
	 * @时间复杂度 O(n)
	 * @param root
	 * @return
	 */
	public BinarySearchTreeNode<Integer> findMinNoRecursion(BinarySearchTreeNode<Integer> root){
		if(root == null){
			return null;
		}
		
		while (root.getLeft() != null) {
			root = root.getLeft();
		}
		
		return root;
	}
	
	/**
	 * 在二叉搜索树中查找最大元素
	 * 思路：
	 * 		根据二叉搜索树的定义最右边的节点为最大元素
	 * @时间复杂度 O(n)
	 * @param root
	 * @param data
	 * @return
	 */
	public BinarySearchTreeNode<Integer> findMax(BinarySearchTreeNode<Integer> root){
		if(root == null){
			return null;
		}
		
		if(root.getRight() == null){
			return root;
		}else{
			return findMax(root.getRight());
		}
	}
	
	/**
	 * 非递归版本：在二叉搜索树中查找最大元素
	 * @时间复杂度 O(n)
	 * @param root
	 * @return
	 */
	public BinarySearchTreeNode<Integer> findMaxNoRecursion(BinarySearchTreeNode<Integer> root){
		if(root == null){
			return null;
		}
		
		while (root.getRight() != null) {
			root = root.getRight();
		}
		
		return root;
	}
	
	/**
	 * 在二叉搜索树中插入元素
	 * 思路：
	 * 		找到目标元素所属的正常位置，然后在那个叶子节点处插入该元素
	 * @时间复杂度 O(n)
	 * @param root
	 * @param data
	 * @return
	 */
	public BinarySearchTreeNode<Integer> insert(BinarySearchTreeNode<Integer> root,int data){
		if(root == null){
			root = new BinarySearchTreeNode<Integer>(data);
		}else{
			if(data < root.getData().intValue()){ //在它的左子树的某处插入该元素
				root.setLeft(insert(root.getLeft(), data));
			}else if(data > root.getData().intValue()){ //在它的右子树的某处插入该元素
				root.setRight(insert(root.getRight(), data));
			}
		}
		
		return root;
	}
	
	/**
	 * 在二叉树搜索树中删除元素
	 * 思路：
	 * 		1. 如果待删除元素为叶子节点，则返回NULL给其双亲节点
	 * 		2. 如果待删除元素只有一个孩子节点，则将待删元素的孩子节点返回给其双亲节点
	 * 		3. 如果待删除元素有两个孩子节点，则将待删元素的左子树中的最大值（或右子树中的最小值）返回给其双亲节点
	 * @时间复杂度 O(n)
	 * @param root
	 * @param data
	 * @return
	 */
	public BinarySearchTreeNode<Integer> delete(BinarySearchTreeNode<Integer> root,int data){
		if(root == null){
			throw new RuntimeException("Element not in this tree");
		}else{
			if(data < root.getData().intValue()){ //待删除元素在它的左子树的某处
				root.setLeft(delete(root.getLeft(), data));
			}else if(data > root.getData().intValue()){ //待删除元素在它的右子树的某处
				root.setRight(delete(root.getRight(), data));
			}else{ //找到待删除元素
				//待删除元素有两个孩子节点
				if(root.getLeft() != null && root.getRight() != null){
					BinarySearchTreeNode<Integer> tmpLeftNode = root.getLeft(); //左孩子节点
					
					//找到子树tmpLeftNode的最大元素
					while (tmpLeftNode.getRight() != null) {
						tmpLeftNode = tmpLeftNode.getRight();
					}
					
					root.setData(tmpLeftNode.getData());
					
					//删除左子树中的这个最大值——tmpLeftNode
					root.setLeft(delete(root.getLeft(), root.getData()));
				}else{ //待删除元素有一个孩子节点或没有孩子节点
					if(root.getLeft() != null){
						root = root.getLeft();
					}else if(root.getRight() != null){
						root = root.getRight();
					}else{ //待删除元素为叶子节点
						root = null;
					}
				}
			}
		}
		
		return root;
	}
	
	
	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 使用队列构造一个供测试使用的二叉树
		 *     6
		 *   2    8
		 * 1  4  7  9
		 *   3 5  
		 */
		BinarySearchTreeNode<Integer> node3 = new BinarySearchTreeNode<Integer>(3);
		BinarySearchTreeNode<Integer> node5 = new BinarySearchTreeNode<Integer>(5);
		BinarySearchTreeNode<Integer> node4 = new BinarySearchTreeNode<Integer>(4, node3, node5);
		BinarySearchTreeNode<Integer> node1 = new BinarySearchTreeNode<Integer>(1);
		BinarySearchTreeNode<Integer> node7 = new BinarySearchTreeNode<Integer>(7);
		BinarySearchTreeNode<Integer> node9 = new BinarySearchTreeNode<Integer>(9);
		BinarySearchTreeNode<Integer> node2 = new BinarySearchTreeNode<Integer>(2, node1, node4);
		BinarySearchTreeNode<Integer> node8 = new BinarySearchTreeNode<Integer>(8, node7, node9);
		
		BinarySearchTreeNode<Integer> root = new BinarySearchTreeNode<Integer>(6, node2, node8);
		
		//中序遍历二叉搜索树
		pirntByInOrder(root);
		System.out.println();
		
		//在二叉搜索树中查找元素
		BinarySearchTreeNode<Integer>  result = findData(root,4);
		System.out.println(result.getData());
		
		//非递归版本：在二叉搜索树中查找元素
		result = findDataNoRecursion(root,4);
		System.out.println(result.getData());
		
		//在二叉搜索树中查找最小元素
		System.out.println("最小元素是：" + findMin(root).getData());
		
		//非递归版本：在二叉搜索树中查找最小元素
		System.out.println("最小元素是：" + findMinNoRecursion(root).getData());

		//在二叉搜索树中查找最大元素
		System.out.println("最大元素是：" + findMax(root).getData());
		
		//非递归版本：在二叉搜索树中查找最大元素
		System.out.println("最大元素是：" + findMaxNoRecursion(root).getData());
		
		//在二叉搜索树中插入元素
		BinarySearchTreeNode<Integer> insertedRoot = insert(root,0);
		pirntByInOrder(insertedRoot);
		System.out.println();
		
		//在二叉树搜索树中删除元素
		BinarySearchTreeNode<Integer> deletedRoot = delete(root,4);
		pirntByInOrder(deletedRoot);

	}
}
